package org.example.myleet.p402;

import java.util.List;
import java.util.Stack;

public class Solution {
    public String removeKdigits(String num, int k) {
        int toBeRemoved = k;
        char[] numCharSeq = num.toCharArray();
        Stack<Character> stack = new Stack<>();
        stack.push(numCharSeq[0]);
        for (int i=1; i<numCharSeq.length; i++) {
            while (!stack.isEmpty() && (numCharSeq[i] < stack.peek() && toBeRemoved > 0)) {
                //比较大，值得剔除
                stack.pop();
                --toBeRemoved;
            };
            stack.push(numCharSeq[i]);
        }
        //在剩下的字符列表中取前n-k个字符作为结果，前导0需要剔除
        List<Character> remainCharList = stack.subList(0, numCharSeq.length - k);
        if (remainCharList.size() < 1) {
            return "0";
        } else {
            StringBuilder sb = new StringBuilder();
            int remainSize = remainCharList.size();
            for (int i=0; i<remainSize; i++) {
                char c = remainCharList.get(i);
                if ('0' < c) {
                    sb.append(c);
                } else if (sb.length()>0) {
                    sb.append(c);
                }
            }
            if (sb.length() < 1) {
                sb.append(remainCharList.get(remainSize-1));
            }
            return sb.toString();
        }
    }
}
